package string;

/**
 * 给定一个全是小写字母的字符串str，删除多余字符，使得每种字符只保留一个，并让最终结果字符串的字典序最小
 * 【举例】
 * str = "acbc"，删掉第一个'c'，得到"abc"，是所有结果字符串中字典序最小的。
 * str = "dbcacbca"，删掉第一个'b'、第一个'c'、第二个'c'、第二个'a'，得到"dabc"是所有结果字符串中字典序最小的。
 * <p>
 * 时间复杂度：O（k * n） n 为字符串长度，k 为字符种类。 因为，每次选出一个字符都需要遍历一次
 *
 * @author Liaorun
 */
public class RemoveDuplicateLettersLessLexi {

    public static void main(String[] args) {
        System.out.println(remove("acbc"));
        System.out.println(remove("dbcacbca"));
    }

    public static String remove(String str) {
        if (str == null || str.length() < 2) {
            return str;
        }

        int[] map = new int[256];
        // 建立词频表
        for (int i = 0; i < str.length(); i++) {
            map[str.charAt(i)]++;
        }
        // 记录变量到的字符中ASCll码最小的字符下标
        int minACSIndex = 0;
        for (int i = 0; i < str.length(); i++) {
            if (--map[str.charAt(i)] == 0) {
                // 当前字符的词频变为0了
                // 检查更新遇到的ASCll码最小的字符下标
                minACSIndex = str.charAt(minACSIndex) > str.charAt(i) ? i : minACSIndex;
                break;
            } else {
                // 当前字符的词频 > 0
                // 检查更新遇到的ASCll码最小的字符下标
                minACSIndex = str.charAt(minACSIndex) > str.charAt(i) ? i : minACSIndex;
            }
        }

        return str.charAt(minACSIndex) + remove(str.substring(minACSIndex + 1).replaceAll(String.valueOf(str.charAt(minACSIndex)), ""));
    }
}
